When storing text that should not be seen by a third party as electronic data, the data is encrypted and transformed such that it cannot be decrypted without knowing a password. An encryption method called a block cipher of segmenting data into fixed sized blocks and encrypting the respective blocks using a specified function dependant on a secret key, and a decryption method called a stream cipher of encrypting using different functions according to position of data are currently widely used as the cryptographic technology. With the stream cipher, data and a cryptographic random number sequence are often exclusive-ORed.
Even when using electronic commerce over the Internet, data is encrypted and then transmitted in order to securely conduct communication between two points A and B without being known by a third party. A shared key encryption method represented by DES, Triple DES, or AES is currently widely used as the cryptographic technology for such transmission. This is a method for transforming data to be transmitted, into data a third party cannot interpret based on a shared encryption key shared only by A and B between which communication is conducted.
DES (Data Encryption Standard) is a shared key encryption method recommended as a standard for data encryption by the US National Institute of Standards and Technology (NIST). Triple DES is an encryption method increasing security by repeating DES three times. AES (Advanced Encryption Standard) is an encryption method called Rijindael developed by mathematicians J. Daemen and V. Rijimen and publicly offered by NIST as a standard for data encryption instead of DES. All of these methods are shared key encryption methods or block ciphers encrypting segmented, fixed size blocks of data at a high speed using a shared key. Computation amount required for this conversion is extremely small, and thus very practical.
For the stream cipher, a method of generating a cryptographic random number sequence through Blum-Blum-Shub (BBS), which generates pseudorandom numbers using quadratic residuosity, and taking exclusive-OR with the text to obtain a cipher text is widely known. BBS repeats squaring an encryption key k and conducting modulo operation: the resulting squared number mod N, thereby providing respective residues, where N is a product of two secret prime numbers, and then arranges the least significant bits thereof to make a cryptographic random number sequence. ‘L. Blum, M. Blum, M. Shub: “A Simple Unpredictable Pseudo-Random Number Generator”, SIAM J. Comput. Vol 15, No. 2, May 1986’ shows that the resulting cryptographic random number sequence is extremely cryptographically excellent as long as N is sufficiently large, in other words, the resulting pseudorandom number sequence has a property that predicting the next bit at a better probability than by random is difficult even if it is made from collected, multiple successive pieces of data. Therefore, it is considered that use of this causes it extremely difficult to find a rule even if many letters are estimated, and computations equal to complete checking is required to estimate other substrings.
However, since the block cipher according to the conventional shared key encryption method creates a complicated encryption function based on key information and then transforms plaintext using the created function, a problem that a fast cryptosystem creates one-sided functions and thus information for deciphering is easily obtained develops. For example, when trying to decipher a code, attacking through encryption of a well-known plaintext using differential cryptanalysis, linear cryptanalysis or the like is often used. In other words, there is a problem that in a situation where an attacker is capable of encrypting an arbitrary text, data used for encryption is collected and thus the code is broken more easily than by searching all keys. Furthermore, even with the shared key encryption method stream ciphers, as it is slow to compute the square of a large number and residue for that value or a large number N through the aforementioned BBS, for example, there is a problem that computation for generating a sufficiently secure cryptographic random number sequence is extremely slow, and a pseudorandom number quickly generated is not cryptographically secure.
Moreover, there is a problem that a currently well-known cryptographic random number sequence for a stream cipher has a short period and therefore cannot be used for a long time.
Methods for coping with these problems are given in Patent Documents 1 through 5, for example. In Patent Document 1 and Patent Document 2, preparing multiple encryption functions, selecting one of the encryption functions based upon key data or data from the outside, and encrypting using that selected one that is different for each plaintext allows prevention of leakage of information and allows authentication. In Patent Documents 3 through 5, how to create a cryptographic random number sequence with excellent properties is provided. Particularly in Patent Document 3, a cryptographic random number sequence is generated after having rewritten a plaintext sequence through finite-state automaton, which is strongly tied to the present invention. Although it is a pseudorandom number generator based on a linear feedback shift register (LFSR), there is a problem that processing speed when software is implemented is insufficient. Furthermore, conventional technology regarding the pseudorandom number generator based on LFSR is disclosed in ‘B. Schneier, “Applied Cryptography,” John Wiley & Sons, Inc., 1996. pp. 369-428’.    Patent Document 1: Japanese Unexamined Patent Application Publication No. Hei 11-15940    Patent Document 2: Japanese Unexamined Patent Application Publication No. Hei 11-265146    Patent Document 3: Japanese Unexamined Patent Application Publication No. Hei 11-500849    Patent Document 4: Japanese Unexamined Patent Application Publication No. 2003-37482    Patent Document 5: Japanese Unexamined Patent Application Publication No. 2004-38020